import java.util.*;
public class WinterHolidayHomework {

//    private List<Integer> path = new ArrayList<>();
//    private List<List<Integer>> ans = new ArrayList<>();

//    private void DFS(int index, int[] nums){
//        if(index > nums.length){
//            return;
//        }
//        ans.add(new ArrayList<>(path));
//        for(int i = index; i < nums.length; i++){
//            path.add(nums[i]);
//            DFS(i + 1, nums);
//            path.remove(path.size() - 1);
//        }
//
//    }

//    private void DFS(int index, int[] nums){
//        if(index == nums.length){
//            ans.add(new ArrayList<>(path));
//            return;
//        }
//        path.add(nums[index]);
//        DFS(index + 1, nums);
//        path.remove(path.size() - 1);
//        DFS(index + 1, nums);
//    }
//    public List<List<Integer>> subsets(int[] nums) {
//        DFS(0, nums);
//        return ans;
//    }

//    private void DFS(int index, int n, int k){
//        if(path.size() == k){
//            ans.add(new ArrayList<>(path));
//            return;
//        }
//        for(int i = index; i <= n; i++){
//            path.add(i);
//            DFS(i + 1, n, k);
//            path.remove(path.size() - 1);
//        }
//    }
//    public List<List<Integer>> combine(int n, int k) {
//        DFS(1, n, k);
//        return ans;
//    }
//    private boolean[] isUsed = new boolean[21];
//    private List<Integer> path = new ArrayList<>();
//    private List<List<Integer>> ret = new ArrayList<>();
//    public List<List<Integer>> permuteUnique(int[] nums) {
//        DFS(nums);
//        return ret;
//    }
//
//    private void DFS(int[] nums){
//        Arrays.sort(nums);
//        if(path.size() == nums.length){
//            ret.add(new ArrayList<>(path));
//            return;
//        }
//
//        for(int i = 0; i < nums.length; i++){
//            if(i > 0 && nums[i] != nums[i - 1] && isUsed[i - 1] == false){
//                if(isUsed[i]==false){
//                    path.add(nums[i]);
//                    isUsed[i]=true;
//                    DFS(nums);
//                    isUsed[i] = false;
//                    path.remove(path.size() - 1);
//                }
//            }
//        }
//    }
    private StringBuilder stringBuilder = new StringBuilder();
    private List<String> ret = new ArrayList<>();

    private void DFS(int left, int right){
        if(left == 0 && right == 0){
            ret.add(new String(stringBuilder));
            return;
        }
        if(left <= right){
            if(left > 0){
                stringBuilder.append("(");
                DFS(left - 1, right);
                stringBuilder.deleteCharAt(stringBuilder.length() - 1);
            }

            if(right > 0){
                stringBuilder.append(")");
                DFS(left, right - 1);
                stringBuilder.deleteCharAt(stringBuilder.length() - 1);
            }
        }
        return;
    }

    public List<String> generateParenthesis(int n) {
        DFS(n, n);
        return ret;
    }

    public static void main(String[] args) {
        WinterHolidayHomework winterHolidayHomework = new WinterHolidayHomework();
        winterHolidayHomework.generateParenthesis(2);
    }
}
